package com.mdnote.practice.devide_and_rule;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description Pwo(x, n)
 */
public class LeetCode50 {


    public static void main(String[] args) {
        LeetCode50 leetCode50 = new LeetCode50();
        double res = leetCode50.myPow(2, 11);
        System.out.println(res);
    }

    public double myPow(double x, int n) {
        // 如果x为0直接返回0
        if (x == 0) {
            return 0;
        }
        // 如果x为负数，我们x变成倒数
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }

        return pow(x, n);


    }

    private double pow(double x, int n) {
        // Terminator 最后都是1 / 2的了
        if (n == 1) {
            return x;
        }
        // process current logic(split big question) & drill down
        double middleRes = pow(x, n / 2);
        // merge
        if (n % 2 == 0) {
            return middleRes * middleRes;
        } else {
            return middleRes * middleRes * x;
        }
        // restore current data
    }
}
